//
// Description: 239. 滑动窗口最大值
// Created by Loading on 2021/9/20.
//

#include <bits/stdc++.h>

using namespace std;

vector<int> maxSlidingWindow(vector<int> &nums, int k) {
    int n = nums.size();
    // 优先级队列，存储 <值，下标>
    priority_queue<pair<int, int>> q;
    vector<int> res;

    for (int i = 0; i < k; ++i) {
        q.emplace(nums[i], i);
    }
    res.emplace_back(q.top().first);

    for (int i = k; i < n; ++i) {
        // 队列中的最大值已不在窗口内，移除
        while (!q.empty() && q.top().second <= i - k) {
            q.pop();
        }
        q.emplace(nums[i], i);
        res.emplace_back(q.top().first);
    }

    return res;
}

int main() {
    vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7, 6, 4, 3, 2, 4, 6, 54, 8, 5, 4};
    int k = 3;
    vector<int> res = maxSlidingWindow(nums, k);
    for (auto &x : res) {
        cout << x << " ";
    }
    cout << endl;

    return 0;
}
